package main.Q401_500;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class Q421_430 {
    public static void main(String[] args) {
        System.out.println("Question421：数组中两个数的最大异或值");
        System.out.println("Question422：");
        System.out.println("Question423：从英文中重建数字");
        System.out.println("Question424：替换后的最长重复字符");
        System.out.println("Question425：");
        System.out.println("Question426：");
        System.out.println("Question427：");
        System.out.println("Question428：");
        System.out.println("Question429：N叉树的层序遍历");
        System.out.println("Question430：扁平化多级双向链表");
    }
}

class Node {
    public int val;
    public Node prev;
    public Node next;
    public Node child;
};

//class Node {
//    public int val;
//    public List<Node> children;
//    public Node() {}
//    public Node(int _val) {
//        val = _val;
//    }
//    public Node(int _val, List<Node> _children) {
//        val = _val;
//        children = _children;
//    }
//};
class Question421{
    int s[][];
    int idx;
    public int findMaximumXOR(int[] nums) {
        int n=nums.length;
        s=new int[31*n][2];
        int res=0;
        for(int num:nums) insert(num);
        for(int num:nums) res=Math.max(res,query(num));
        return res;
    }
    private void insert(int x) {
        int p=0;
        for(int i=30;i>=0;i--) {
            int u=x>>i&1;
            if(s[p][u]==0) s[p][u]=++idx;
            p=s[p][u];
        }
    }
    private int query(int x) {
        int p=0;
        int res=0;
        for(int i=30;i>=0;i--) {
            int u=x>>i&1;
            if(s[p][u^1]!=0) {
                res+=1<<i;
                p=s[p][u^1];
            }
            else p=s[p][u];
        }
        return res;
    }
}

class Question423{
    public String originalDigits(String s) {
        Map<Character,Integer> map=new HashMap<>();
        char[] str=s.toCharArray();
        for (char c:str) map.put(c,map.getOrDefault(c,0)+1);
        int[] con=new int[10];
        con[0]=map.getOrDefault('z',0);
        con[2]=map.getOrDefault('w',0);
        con[4]=map.getOrDefault('u',0);
        con[6]=map.getOrDefault('x',0);
        con[8]=map.getOrDefault('g',0);
        con[7]=map.getOrDefault('s',0)-con[6];
        con[5]=map.getOrDefault('f',0)-con[4];
        con[3]=map.getOrDefault('h',0)-con[8];
        con[9]=map.getOrDefault('i',0)-con[6]-con[5]-con[8];
        con[1]=map.getOrDefault('o',0)-con[0]-con[2]-con[4];
        StringBuffer result=new StringBuffer();
        for (int i=0;i< con.length;i++){
            while (con[i]-->0) result.append(i);
        }
        return result.toString();
    }
}

class Question424{
    public int characterReplacement(String s, int k) {
        int length=s.length();
        if (length<2) return length;
        char[] str=s.toCharArray();
        int left=0,right=0,maxCount=0,result=0;
        int[] counts=new int[26];
        while (right<length){
            counts[str[right]-'A']++;
            maxCount=Math.max(maxCount,counts[str[right++]-'A']);
            if (right-left>maxCount+k){
                counts[str[left]-'A']--;
                left++;
            }
            result=Math.max(result,right-left);
        }
        return result;
    }
}

class Question429{
    public List<List<Integer>> levelOrder(Node root) {
        List<List<Integer>> list=new ArrayList<>();
//        if (root!=null){
//            Queue<Node> queue=new LinkedList<>();
//            queue.add(root);
//            while (!queue.isEmpty()){
//                int size= queue.size();
//                List<Integer> tempList=new ArrayList<>();
//                for (int i=0;i<size;i++){
//                    Node curNode=queue.poll();
//                    tempList.add(curNode.val);
//                    for (Node nextNode: curNode.children) queue.add(nextNode);
//                }
//                list.add(tempList);
//            }
//        }
        return list;
    }
}

class Question430{
    public Node process(Node head){
        Node cur=head,last=null;
        while (cur!=null){
            Node next=cur.next;
            if (cur.child!=null){
                Node childLast=process(cur.child);
                next=cur.next;
                cur.next=cur.child;//连入子级链表
                cur.child.prev=cur;
                if (next!=null){//子级链表连入父级下一节点
                    childLast.next=next;
                    next.prev=childLast;
                }
                cur.child=null;
                last=childLast;
            }else {
                last=cur;
            }
            cur=next;
        }
        return last;
    }
    public Node flatten(Node head) {
        process(head);
        return head;
    }
}